package com.example.slidingwindow;

import java.util.*;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。
 * 滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
 *
 *  示例 1：
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 *
 *  示例 2：
 * 输入：nums = [1], k = 1
 * 输出：[1]
 *
 *  示例 3：
 * 输入：nums = [1,-1], k = 1
 * 输出：[1,-1]
 */
public class Leetcode239_Offer59_MaxSlidingWindow {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1, 2, 0, 5};
        int k = 3;
        int[] res = new Solution().maxSlidingWindow(nums, k);
        for (int r : res) {
            System.out.print(r + ", ");
        }

    }
    static class Solution {
        /**
         * 解法三:单调递减队列
         * 单调队列 队列必须满足从队头到队尾的严格单调性。(常用于需要得到当前的某个范围内的最小值或最大值。)
         *
         * 使用一个队列存储所有还没有被移除的下标。在队列中，下标按照从小到大的顺序被存储且它们在数组 nums中对应的值是严格单调递减的
         * 当滑动窗口向右移动时，把一个新的元素放入队列中。
         * 为了保持队列的性质，需要不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，将其弹出队列。
         * 不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
         *
         * 由于队列中  下标对应的元素  是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。
         * 但与方法二中相同的是，此时的最大值可能在滑动窗口左边界的左侧，并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。
         * 因此还需要不断从队首弹出元素，直到队首元素在窗口中为止。
         *
         * @param nums
         * @param k
         * @return
         */
        private int[] maxSlidingWindow3(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> deque = new LinkedList<>();
            // 初始化最开始的窗口
            for (int i = 0; i < k; ++i) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
            res[0] = nums[deque.peekFirst()];
            for (int i = k; i < nums.length; ++i) {
                while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { // 为了维持整个队列对应的数组元素是单减的
                    deque.pollLast();
                }
                deque.offerLast(i);

                while (deque.peekFirst() <= i - k) {// 队头的元素可已经不在窗口内了,就应该将它们出队
                    deque.pollFirst();
                }
                res[i - k + 1] = nums[deque.peekFirst()];
            }
            return res;
        }

        /**
         * 通过堆求最大值
         * @param nums
         * @param k
         * @return
         */
        private int[] maxSlidingWindow2(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            // 方式一超时(remove需要遍历 时间复杂度为O(n^2))
            // 初始化将前k个元素入堆
//            Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
//            for (int i = 0; i < k; i++) {
//                maxHeap.offer(nums[i]);
//            }
//            res[0] = maxHeap.peek();
//            for (int i = k; i < nums.length; i++) {
//                maxHeap.remove(nums[i - k]);
//                maxHeap.offer(nums[i]);
//                res[i - k + 1] = maxHeap.peek();
//            }


            // 方式二:去掉remove方式可行
            Queue<int[]> maxHeap = new PriorityQueue<>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
            for (int i = 0; i < k; i++) {
                maxHeap.offer(new int[] {nums[i], i});
            }
            res[0] = maxHeap.peek()[0];

            for (int i = k; i < nums.length; i++) {
                maxHeap.offer(new int[] {nums[i], i});
                while (maxHeap.peek()[1] <= i - k) { // 当堆中最大值为窗口以外的元素时,将其移除
                    maxHeap.poll();
                }
                res[i - k + 1] = maxHeap.peek()[0]; // 将当前窗口最大值加入到集合中
            }
            return res;
        }

        /**
         * 解法一:暴力法(超时)
         * 拿到一个窗口的所有值然后就进行排序,将最大的值加入到结果集中
         * @param nums
         * @param k
         * @return
         */
        private int[] maxSlidingWindow1(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];

            for (int r = k - 1, l = 0; r < nums.length; r++) {
                int[] windowArr = new int[k];
                System.arraycopy(nums, l, windowArr, 0, k);
                Arrays.sort(windowArr);
                res[l] = windowArr[k - 1];
                l++;
            }
            return res;
        }

        public int[] maxSlidingWindow(int[] nums, int k) {
            return maxSlidingWindow3(nums, k);
        }
    }
}
